package Offer;


public class Test16 
{

	public static void main(String[] args) 
	{
		ListNode p1 = new ListNode(1);
		ListNode p2 = new ListNode(2);
		ListNode p3 = new ListNode(3);
		ListNode p4 = new ListNode(4);
//		p1.next=p2;
//		p2.next=p3;
//		p3.next=p4;
		p4.next=null;
//		System.out.println(reverseList(p1).value);
		System.out.println(ReverseLinked.reverseLinkedList(p1).value);
	}
    public static ListNode reverseList(ListNode head)
    {
    	if(head==null||head.next==null)
    		return head;   	  	
    	ListNode pre = head;
    	ListNode p= head.next;
    	pre.next=null;
    	ListNode nxt=null;
    	while(p!=null)
    	{
    		nxt=p.next;
    		p.next=pre;
    		pre=p;
    		p=nxt;
    	}
    	return pre;
    }
}

class ReverseLinked{
	public static ListNode reverseLinkedList(ListNode head){
		if(head == null || head.next == null){
			return head;
		}
		ListNode reverseHeadNode = null;
		ListNode preNode = null;
		ListNode nextNode = head;
		while(nextNode != null){
			ListNode tmpNode = nextNode.next;
			nextNode.next = preNode;
			if (tmpNode == null) {
				reverseHeadNode = nextNode;
			}
			preNode = nextNode;
			nextNode = tmpNode;
		}
		return reverseHeadNode;
	}
}
